package com.yww.datastructure.line.linkedlist;

import com.yww.datastructure.line.Linear;

import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.Stream;

/**
 * @author yww
 * @description 单向链表 带哨兵
 * @since 2024/1/30 14:21
 */
public final class SingleLinkedListSentinel<E> implements Linear<E> {
    // 头指针，带哨兵
    private final Node<E> head = new Node<>(null, null);

    @Override
    public void addLast(E e) {
        Node<E> last = findLast();
        last.next = new Node<>(e, null);
    }

    @Override
    public void addFirst(E e) {
        add(e, 0);
    }

    @Override
    public void add(E e, int index) {
        // 找到前一个节点，index=0时返回的是哨兵
        Node<E> pre = find(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        pre.next = new Node<>(e, pre.next);
    }

    public E get(int index) {
        Node<E> find = find(index);
        if (find == null) {
            throw illegalIndex(index);
        }
        return find.value;
    }


    @Override
    public void foreach(Consumer<E> consumer) {
        for (Node<E> p = this.head.next; p != null; p = p.next) {
            consumer.accept(p.value);
        }
    }

    public void loop(Consumer<E> consumer) {
        Node<E> p = this.head.next;

        while (p != null) {
            consumer.accept(p.value);
            p = p.next;
        }
    }

    @Override
    public Stream<E> stream() {
        Stream.Builder<E> builder = Stream.builder();
        foreach(builder::add);
        return builder.build();
    }

    public E removeFirst() {
        Node<E> p = head.next;
        if (p == null) {
            throw illegalIndex(0);
        }
        head.next = p.next;
        return p.value;
    }

    @Override
    public E remove(int index) {
        // 找到前驱
        Node<E> pre = find(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        // 待删除节点
        Node<E> removed = pre.next;
        if (removed == null) {
            throw illegalIndex(index);
        }
        pre.next = removed.next;
        return removed.value;
    }

    public int size() {
        Node<E> p = this.head.next;
        int i = 0;
        while (p != null) {
            i++;
            p = p.next;
        }
        return i;
    }

    @Override
    public E removeLast() {

        return remove(size() - 1);
    }

    @Override
    public boolean isEmpty() {
        return head.next == null;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;

            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E res = p.value;
                p = p.next;
                return res;
            }
        };
    }

    /**
     * 获取最后一个节点
     **/
    private Node<E> findLast() {
        Node<E> p = head;
        while (p.next != null) {
            p = p.next;
        }
        return p;
    }

    /**
     * 获取指定索引的节点
     */
    private Node<E> find(int index) {
        Node<E> p = head;
        for (int i = -1; p != null; i++, p = p.next) {
            if (index == i) {
                return p;
            }
        }
        return null;
    }

    /**
     * 节点类 value|next
     **/
    private static class Node<E> {
        private final E value;
        private Node<E> next;

        // 方便进行插入
        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }
}
